package niuke.week02;

import java.util.HashSet;
import java.util.Set;

/**
 给定彼此独立的两棵二叉树，树上的节点值两两不同，判断 t1 树是否有与 t2 树完全相同的子树。

 子树指一棵树的某个节点的全部后继节点
 {1,2,3,4,5,6,7,#,8,9}
   {2,  4,5,#,   8,9}

 true
 */
public class ContainsTree {
    public static class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public static String preOrder (TreeNode root) {
        if (root == null){
            return "#"+" ";
        }
        return  root.val+" "+preOrder(root.left)+preOrder(root.right);
    }

    public static  boolean isContains1 (TreeNode root1, TreeNode root2) {

        String[] s1 =  preOrder(root1).split(" ");
        String[] s2 =  preOrder(root2).split(" ");

        if(s1.length>s2.length)
            return  kmpSearch(s1,s2).size()>0;
        else
           return kmpSearch(s2,s1).size()>0;

    }
//递归的解法
    public static  boolean isContains2 (TreeNode root1, TreeNode root2) {

       if(root1==null ||root2==null)
           return  false;

        return isContains2(root1.left,root2) || isContains2(root1.right,root2) || isSmaeTree(root1,root2);

    }
    public static  boolean isSmaeTree (TreeNode root1, TreeNode root2){
        if(root1==null && root2==null)
            return  true;
        if (root1==null || root2==null || root1.val!= root2.val)
            return false;
        return isSmaeTree(root1.left,root2.left) && isSmaeTree(root1.right,root2.right) && root1.val== root2.val;


    }



    public static void main(String[] args) {
        TreeNode node3 = new TreeNode(2, new TreeNode(1), new TreeNode(1));
        TreeNode node2 = new TreeNode(2, new TreeNode(1), null);
        TreeNode node1 = new TreeNode(3, node3, new TreeNode(4));

        System.out.println(isContains2(node1,node3));
        System.out.println(isContains2(node1,node2));


    }

    public static Set<Integer> kmpSearch(String[] text,String[]  parttern){
        HashSet<Integer> set = new HashSet<>();
//        text[i]      m = len(text)
//        parttern[j]   n = len(parttern)
        int[] prefix = getPrefix(parttern);
        int[] next = movePrefix(prefix);
        int m = text.length;
        int n = parttern.length;

        int i=0,j=0;
        while (i<m){
            if(j==n-1 && parttern[j].equals(text[i])){
                set.add(i-j);
                j=next[j];
            }

            if(text[i].equals(parttern[j])){//匹配上了
                i++;
                j++;
            }else {//吧pattern罗过来
                j = next[j];
                if(j==-1){//如果是第一个字符
                    i++;
                    j++;
                }
            }
        }
        return set;
    }

    public static int [] movePrefix(int[] prefix){
        int []next = new int[prefix.length];
        //源数组，源数组要复制的起始位置，目标数组，源数组要复制的起始位置,要复制的长度。
        System.arraycopy(prefix, 0, next, 1, prefix.length-1);
        next[0] = -1;
        return next;
    }

    public static int[] getPrefix(String []str){
        int n = str.length;
        int[]dp = new int[n];

        for (int i = 1; i < n; i++) {
            if(str[i].equals(str[dp[i - 1]]))
                dp[i] = dp[i-1]+1;// A B A A B A
            else if(!str[i].equals(str[0]))  //A B A B C
                dp[i] = 0;
            else dp[i] = 1;//A B A B A

        }
        return dp;
    }
}